﻿using System;

namespace IndexedFilePackageLibrary
{

    static class BTree
    {
        public static BTreeNode<T, TNodeData> FromSortedArray<T, TNodeData>(T[] array, int maxItemCount)
        {
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }
            if (maxItemCount <= 0)
            {
                throw new ArgumentOutOfRangeException(nameof(maxItemCount));
            }

            var info = new BTreeInfo(maxItemCount);
            return InternalBuildNode<T, TNodeData>(array, 0, array.Length, ref info);
        }
        public static BTreeNode<T, TNodeData> FromSortedArray<T, TNodeData>(T[] array, int startIndex, int count, int maxItemCount)
        {
            if (array == null)
            {
                throw new ArgumentNullException(nameof(array));
            }
            if (startIndex < 0 || startIndex >= array.Length)
            {
                throw new ArgumentOutOfRangeException(nameof(startIndex));
            }
            if (count < 0 || startIndex + count > array.Length)
            {
                throw new ArgumentOutOfRangeException(nameof(count));
            }
            if (maxItemCount <= 0)
            {
                throw new ArgumentOutOfRangeException(nameof(maxItemCount));
            }

            var info = new BTreeInfo(maxItemCount);
            return InternalBuildNode<T, TNodeData>(array, startIndex, count, ref info);
        }

        private static BTreeNode<T, TNodeData> InternalBuildNode<T, TNodeData>(T[] array, int startIndex, int count, ref BTreeInfo info)
        {
            var node = new BTreeNode<T, TNodeData>(ref info);
            if (count <= info.MaxItemCount)
            {
                node.Count = count;
                Array.Copy(array, startIndex, node.Items, 0, count);
                return node;
            }
            node.Count = info.MaxItemCount;
            int subTreeItemCount = (count - node.Count) / (node.Count + 1);
            int lastTreeItemCount = (count - node.Count) - subTreeItemCount * node.Count;
            for (int i = 0; i < node.Count; i++)
            {
                if (subTreeItemCount > 0)
                {
                    node.LeftNodes[i] = InternalBuildNode<T, TNodeData>(array, startIndex, subTreeItemCount, ref info);
                    startIndex += subTreeItemCount;
                }
                node.Items[i] = array[startIndex++];
            }
            if (lastTreeItemCount > 0)
            {
                node.RightNode = InternalBuildNode<T, TNodeData>(array, startIndex, lastTreeItemCount, ref info);
            }
            return node;
        }
    }

    class BTreeNode<T, TNodeData>
    {
        /// <summary>
        /// 当前节点内元素数量
        /// </summary>
        public int Count { get; set; }
        private T[] _items;
        public ref T[] Items => ref _items;
        private BTreeNode<T, TNodeData>[] _leftNodes;
        public ref BTreeNode<T, TNodeData>[] LeftNodes => ref _leftNodes;
        public BTreeNode<T, TNodeData> RightNode { get; set; }

        public TNodeData NodeData;

        public BTreeNode(ref BTreeInfo treeInfo)
        {
            _items = new T[treeInfo.MaxItemCount];
            _leftNodes = new BTreeNode<T, TNodeData>[treeInfo.MaxItemCount];
        }
    }

    struct BTreeInfo
    {
        public int MaxItemCount { get; private set; }
        public BTreeInfo(int maxItemCount)
        {
            MaxItemCount = maxItemCount;
        }
    }
}
